# -*- coding: utf-8 -*-


# 归并排序
def merge(array, start, end, mid):
    temp = [0] * (end - start + 1)
    p1 = start
    p2 = mid + 1
    i = 0
    while p1 <= mid and p2 <= end:
        if array[p1] < array[p2]:
            temp[i] = array[p1]
            p1 += 1
        else:
            temp[i] = array[p2]
            p2 += 1
        i += 1
    while p1 <= mid:
        temp[i] = array[p1]
        i += 1
        p1 += 1
    while p2 <= end:
        temp[i] = array[p2]
        i += 1
        p2 += 1
    array[start:end+1] = temp
    print("start:", start, " end:", end, " mid:", mid, " ", array[start:end + 1])


def merge_partition(array, start, end):
    if start < end:
        mid = (start + end) // 2
        merge_partition(array, start, mid)
        merge_partition(array, mid + 1, end)
        merge(array, start, end, mid)


def merge_sort(array):
    n = len(array)
    merge_partition(array, 0, n - 1)


arr = [5, 4, 7, 9, 3, 8, 2, 1]
print(arr)
merge_sort(arr)
print(arr)
